package LinkedList;

import Utils.ListNode;

/**
 * 返回两个链表的相交节点：秒啊
 * 思路： 假设链表A的长度为a + c, 链表B的长度为 b + c， 则有 a + b + c = b + a + c
 * 因此，当访问链表A的指针访问到链表尾部时，令链表A从B的开头访问B
 * 当链表B的指针访问到链表B的尾部时，令链表B从A的开头访问A,当两者存在公共交点，
 * 必有两者最终相交，且交点为两者相同的点
 * Lettcode 160: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
 */
public class getIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != l2) {
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }
        return l1;
    }
}
